#include "solver.h"

namespace solver
{
    Tree dict;	//Dictionary

    TreeNode::~TreeNode()
    {
        for (int i = 0; i < range ; i++)
            if (next[i])
            {
                delete next[i];
                next[i] = NULL;
            }
    }

    //Insert a word into the dictionary
    void Tree::Insert(wchar_t *ptr)
    {
        TreeNode *cur = root;
        TreeNode *next;

        while (*ptr)
        {
            int i = *ptr++ - 0x430;
            if (i <0 || i >= range) break;
            next = cur->next[i];
            if (!next)
            {
                next = cur->next[i] = new TreeNode;
            }
            cur = next;
        }
        cur->next[range] =(TreeNode*)0x1;	//The flag of terminating node
    }

    //Find a word in the dictionary
    bool Tree::Find(wstring word)
    {
        TreeNode *cur = root;
        TreeNode *next;
        const wchar_t *ptr = word.c_str();
        while (*ptr && cur)
        {
            int i = *ptr++ - 0x430;
            if (i < 0 || i >= range) return 0;
            next = cur->next[i];
            cur = next;
        }
        if (cur && cur->next[range]) return true;
        return false;
    }

    //Create masking field where all empty cells are marked as L'X'
    void Field::CreateMask(const Field &fd)
    {
        if (f) delete f;
        w = fd.w;
        h = fd.h;
        f = new wchar_t[w*h];
        wchar_t *ptr1 = fd.f;
        wchar_t *ptr2 = f;
        for (int i = w*h; i > 0; i--)
            if (*ptr1++ == L' ') *ptr2++ = L'X';
            else *ptr2++ = L' ';
    }

    //Read Field object from stream
    istream &operator >> (istream &stream, const Field &f)
    {
        string str;
        wchar_t *wstr = new wchar_t[MAX_WORD_SIZE + 1];

        for (int i = 0; i < f.Height(); i++)
        {
            getline(stream, str);
            mbstowcs(wstr, str.c_str(), MAX_WORD_SIZE);
            for (wchar_t *p = wstr; *p; p++)
                if (*p == L'_') *p = L' ';
            memcpy(f[i], wstr, f.Width()*sizeof(wchar_t));
        }
        delete wstr;
        return stream;
    }

    //Write Field object to stream
    ostream &operator << (ostream &stream, const Field &f)
    {
        wchar_t *ptr = f.f;
        for (int i = 0; i < f.Height(); i++)
        {
            for (int j = 0; j < f.Width(); j++)
                stream << *ptr++;
            stream << endl;
        }
        return stream;
    }
    class WordFinder
    {
    public:
        Coords org;

        const Field &f;

        Words &result;

        WordStack st;

        WordFinder(const Field &fd, Words &res): f(fd), result(res) {}

        // Internal function used to find all alpha combinations which include originating cell
        void FindWords(Coords c, const Field &mask, bool rev = false)
        {
            mask[c] = L'X';						//Mask used cell
            if (c != org) 						//Do not add originating alpha to resulting string 'cause it's already here
            {
                if (rev)
                {
                	st.first.insert(0, 1, f[c]);
                	st.second.push_front(c);
                }
                else
                {
                	st.first.append(1, f[c]);
                	st.second.push_back(c);
                }

                if (st.first.size()>2 && dict.Find(st.first))	//Ignore combinations consist of less than 3 letters
                {
                    result.push_back(st);
#ifdef __VERBOSE__
#ifdef __WIN32__
                    cout << '.';
#else
                    wcout << L'.';
                    wcout.flush();
#endif
#endif
                }
            }

            if (!rev)
            {
                Field new_mask(mask);			//Create new mask for reverse pass similar to current one
                FindWords(org, new_mask, true);
            }

            //Move left if possible
            if (c.x > 0 && mask[c.y][c.x - 1] != L'X')
                FindWords(Coords(c.x - 1, c.y), mask, rev);
            //Move right
            if (c.x < f.Width() - 1 && mask[c.y][c.x + 1] != L'X')
                FindWords(Coords(c.x + 1, c.y), mask, rev);
            //Move up
            if (c.y > 0 && mask[c.y - 1][c.x] != L'X')
                FindWords(Coords(c.x, c.y - 1), mask, rev);
            //Move down
            if (c.y < f.Height() - 1 && mask[c.y + 1][c.x] != L'X')
                FindWords(Coords(c.x, c.y + 1), mask, rev);

            mask[c] = L' ';						//Unmask cell to make it usable in next passes
            if (c != org)						//Do not remove originating alpha which we haven't added
            {
                if (rev)
                {
                	st.first.erase(st.first.begin());
                	st.second.pop_front();
                }
                else
                {
                	st.first.erase(st.first.end() - 1);
                	st.second.pop_back();
                }
            }
        }
    };
    //Function to be called by user. Finds all available words if one letter whould put on field
    void FindAllWords(const Field &f, Words &result)
    {
        for (int i = 0; i < f.Height(); i++)
            for (int j = 0; j < f.Width(); j++)
            {
                if (f[i][j] == ' ')
                {
                    if ((j > 0 && f[i][j - 1] !=' ') || \
                            (j < f.Width() - 1 && f[i][j + 1] != ' ') || \
                            (i > 0 && f[i - 1][j] != ' ') || \
                            (i < f.Height() - 1 && f[i + 1][j] != ' '))
                    {
                        for (wchar_t c = 0x430; c <= 0x44f; c++)
                        {
                            f[i][j] = c;
                            WordFinder wf(f, result);
                            wf.org.x = j, wf.org.y = i;
                            wf.st.first.reserve(MAX_WORD_SIZE<<1);
                            wf.st.first.append(1, c);	//Append originating alpha to string
                            wf.st.second.push_back(wf.org);
                            Field mask;
                            mask.CreateMask(f);
                            wf.FindWords(wf.org, mask);
                        }
                        f[i][j] = L' ';
                    }
                }
            }
    }

    //Reads dictionary into memory (builds storage suitable for Aho-Korasick like algorithm)
    //Returns true if no error occurs
    bool ReadDictionary(const char *name)
    {
        setlocale(LC_ALL,"");
        ifstream in(name);
        if (!in) return false;
        string str;
        wchar_t *wstr = new wchar_t [MAX_WORD_SIZE + 1];

        while (getline(in, str))
        {
            //Remove last '\r' of pair '\n\r' for Unix
#ifndef __WIN32__
            if (*(str.end() - 1) < 0x20) str.erase(str.end() - 1);
#endif
            mbstowcs(wstr, str.c_str(), MAX_WORD_SIZE);	//Converting multi-byte string to widechar string
            dict.Insert(wstr);
        }
        delete wstr;

        return true;
    }

    void get1stMoveWords(vector<wstring> &words, int len, wstring &str, TreeNode *node)
    {
        static int j = 0;
        if(!node) return;
        j++;
        if(j <= len)
        for(int i = 0; i < range; i++)
        {
            str.append(1, (wchar_t)(0x430 + i));
            get1stMoveWords(words, len, str, node->next[i]);
            str.erase(str.end() - 1);
        }
        else
            if(node->next[range]) words.push_back(str);
        j--;
    }

    void getWords(vector<wstring> &words, int len)
    {
        wstring str;
        get1stMoveWords(words, len, str, dict.getRoot());
    }

    bool searchDict(const wstring &str)
    {
        return dict.Find(str);
    }
};
